package com.dhu.graph.weightGraph;

import com.dhu.graph.basic.edge.Edge;
import com.dhu.graph.basic.GraphImpls.EdgeWeightGraph;
import com.dhu.graph.utils.IndexMinPQ;

/**
 * @ Author ：snow
 * @ Date   ：Created in 2020-05-10
 * @ Description：
 * Prim算法的即时实现
 * 该算法的思想是： 从顶点0 开始，先把顶点0加入树中，然后把0邻接表中的所有边
 * 加入到pq 下一步就是从pq中删除并返回权重最小的边，遍历访问该最小边的邻接表，如果其邻接表中的顶点已经被访问过了，marked = true,
 * 意味着该顶点已经在树中了，这次并不是想延迟实现那样把所有的边都加入到pq中，对于那些已经在pq中的顶点，如果当前的边的权重小于
 * 之前加入的边，就用当前边替换之前的边。
 * @ Modified By：
 * @ Version:
 */
public class PrimMST {
    private boolean [] marked;
    private Edge[] edgeTo; // 树中的边
    private double[] distTo; // distTO[v]树中到v的权重
    private IndexMinPQ<Double> pq;

    public PrimMST(EdgeWeightGraph G){
        int sz = G.V();
        this.marked = new boolean[sz];
        this.distTo = new double[sz];
        this.edgeTo = new Edge[sz];
        this.pq = new IndexMinPQ<Double>(sz);

        for (int i = 0; i < sz; i++){
            distTo[i] = Double.POSITIVE_INFINITY;
        }
        pq.insert(0,0.0);
        distTo[0] = 0.0;

        while(!pq.isEmpty()){
            visit(G, pq.delMin());
        }
    }
    private void visit(EdgeWeightGraph G, int v){
        marked[v] = true;
        for (Edge edge : G.adj(v)) {
            int w = edge.other(v);
            if (marked[w]) continue; // v- w失效

            if (edge.weight() < distTo[w]){
                edgeTo[w] = edge;
                distTo[w] = edge.weight();
                /*
                 w 可能已经被上一个v加到pq中，此时更改意思是: 从当前的v到w的有向路径的权重比前面的v-w的权重要小，
                 所以要把树中到w的路径改成当前v到w的有向路径。如此pq中只保存的是有效路径

                 */
                if (pq.contains(w)) pq.change(w, edge.weight());
                else pq.insert(w, edge.weight());
            }
        }
    }
}
